package org.wj.problem

import org.wj.problem.InorderTraversal.TreeNode

object GenerateTrees {

  def main(args: Array[String]): Unit = {
    val value = generateTrees(5)
    print(value.length)
  }

  def generateTrees(n: Int): List[TreeNode] = {
    if(n == 0) List() else generateTrees(1, n)
  }


  def generateTrees(start: Int, end: Int): List[TreeNode] = {
    if (start > end) return List(null)
    var result = List[TreeNode]()
    for (i <- start to end) {

      val leftTreeList = generateTrees(start, i - 1)
      val rightTreeList = generateTrees(i + 1, end)
      for (leftTree <- leftTreeList) {
        for (rightTree <- rightTreeList) {
          val treeNode = new TreeNode(i)
          treeNode.left = leftTree
          treeNode.right = rightTree
          result = List(treeNode) ::: result
        }
      }
    }
    result
  }


}
